package com.mzy.linear_struct.subject;

import java.util.*;

/**
 * @Author: codermzy
 * @Date: 2024/04/13/23:42
 * @Description:
 */
public class 回文链表 {
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null) return false;
        ListNode cur = head;
        Deque<Integer> deque = new LinkedList<>();

        while (cur != null) {
            deque.add(cur.val);
            cur = cur.next;

        }

        while (!deque.isEmpty()) {
            if (deque.size() == 1) {
                return true;
            }
            if (!deque.removeFirst().equals(deque.removeLast())) {
                return false;
            }
        }

        return true;
    }

    public boolean isPalindrome2(ListNode head) {
        if (head == null) return false;
        List<Integer> list = new ArrayList<>();

        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        int left = 0;
        int right = list.size() - 1;

        while (left <= right) {
            if (!list.get(left).equals(list.get(right))) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }


    public static boolean isPalindrome3(ListNode head) {
        if (head == null) return false;

        ListNode slow = head;
        ListNode fast = head;

        // 找到中点 slow为中点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast != null) {
            slow = slow.next;
        }

        slow = reverseListNode(slow);

        fast = head;
        while (fast != null && slow != null) {
            if (fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }


        //                 f
        // 1,2,2,3,2,1,8,7,6
        //         s
        return true;
    }

    private static ListNode reverseListNode(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(1, null))));

        // while (l1 != null) {
        //     System.out.println(l1.val);
        //     l1 = l1.next;
        // }

        System.out.println(new 回文链表().isPalindrome3(l1));
    }
}
